Give a proof or a counterexample for each of the following two assertions:

\begin{enumerate}
\item[a)] For a flow network with integer capacities, if all edge capacities are even, then there exists a maximum $s-t$ flow such that the amount of flow o each edge is even.
\item[b)] For a flow network with integer capacities, if all edge capacities are odd, then there exists a maximum $s-t$ flow such that the amount of flow on each edge is odd.
\end{enumerate}

\subparagraph{a)}

Because in a graph $G=(V,E)$ the maximum flow is equal to the minimum cut lets have a generic minimum cut:

\begin{center}
\includegraphics[scale=0.5]{gen-cut.png}
\end{center} 

The value of the maximum flow and the aggregate capacity of the cut (minimum) is:

$$c(e_{1})+c(e_{2})+...+c(e_{n})$$

Because all the capacities of the edges are even we know that the amount of maximum flow is:

$$2k_{1}+2k_{2}+...+2k_{n}=2(k_{1}+...+k_{n})$$

So the amount of maximum flow is even. We can assure that there exists at least one of the following two ways of constructing the corresponding residual graph: 

\subparagraph{One augmenting path} We assure that the amount of flow on each of the edges is equal to the maxflow so since the maxflow is even it will be even.

\subparagraph{More than one augmenting path} Suppose we have more than one augmenting paths in the edges of the graph. Then if more than one augmenting path traverse through an edge, we will have $2k_{i}$ flow or any combination of them in it. If the capacity of the edge is higher that amount of maximum flow, then, since the capacities of the edges in minimum cut are even, we know that any combination of flows, created by the maximum capacity of the edges that are in the minimum cut, will be also even. On the other hand, if the edge is limiting the amount of flow of the augmenting path, we know that it is going to be saturated; and because the capacity of the edge is even, we assure that the flow in it is even.

\subparagraph{b)} 

This is not true, because if maxflow is even and all this amount have to go through one edge with higher capacity than the value of the maxflow, this will produce an even flow traversing through that edge. The maxflow is even in case the min-cut contains even number of edges, as all of them have odd capacities saturated. In other words, since all of the capacities are odd, if even number of augmenting paths goes through an edge (each of them with an odd flow, as defined by the edge with the minimum capacity), then the flow in that edge will be even.

\begin{flushleft}
Lets draw a counterexample:
\end{flushleft}

\begin{center}
\includegraphics[scale=0.5]{odd-cut.png} 
\end{center}

We see that in the first edge which begins in the sink which has an odd capacity there is an even amount of flow traversing this edge because there is a even number of augmenting paths going through that edge. Which means that any even combination of flows defined by the minimum cut that traverse an edge of higher capacity will make a even amount of flow.